import java.util.Arrays;

public class HeadMap {
    public int[] elem;
    public int usedSize;

    public void InitHeap(int[] arr){
        elem=new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            this.elem[i]=arr[i];
            this.usedSize++;
        }
    }
    public void creatHeadMap(){  //建立小根堆
        for (int parent=(usedSize-1-1)/2;parent>=0;parent--) {
            shiftDown(parent,usedSize);
        }
    }
    public void creatHeadMap1(){  //建立大根堆
        for (int parent=(usedSize-1-1)/2;parent>=0;parent--) {
            shiftDown2(parent,usedSize);
        }
    }
    private void shiftDown(int parent,int usedSize){

        int child=2*parent+1;
        while(child<usedSize){
            if(child+1<usedSize&&elem[child+1]<elem[child]){
                child++;
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }

        }
    }
    private void shiftDown2(int parent,int usedSize){  //建立大根堆

        int child=2*parent+1;
        while(child<usedSize){
            if(child+1<usedSize&&elem[child+1]>elem[child]){
                child++;
            }
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }

        }
    }

    public void mapInsert(int k){
        if(mapIsFull()){
            elem=grow();
        }
        elem[usedSize]=k;
        usedSize++;
        for (int parent=(usedSize-1-1)/2;parent>=0;parent--) {
            shiftDown(parent,usedSize);
        }
    }
    public boolean mapIsFull(){
        return  elem.length==usedSize;
    }
    public int[] grow(){
       return Arrays.copyOf(elem,elem.length*2);
    }

    public void mapPoll(){
        if(mapIsEmpty()){
            return;
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=elem[0];
        usedSize--;
        /*for (int parent=(usedSize-1-1)/2;parent>=0;parent--) {
            shiftDown(parent,usedSize);
        }
         */
        shiftDown(0,usedSize);
    }
    public boolean mapIsEmpty(){
        return usedSize==0;
    }
    public void mapsort(){
        int end=usedSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown2(0,end);
            end--;
        }
    }
}
